"""
C++ call graph analyzer.

Provides call graph analysis with support for C++ specific features like
virtual functions, templates, function overloading, and inheritance hierarchies.
"""

from typing import Dict, List, Any, Optional, Set, Tuple
from dataclasses import dataclass, field
from collections import defaultdict, deque
import logging

from ...core.error_handler import log_debug, log_info
from ...parsers.cpp.symbol_table import Symbol, SymbolKind, SymbolTable
from .cuda_hip import CudaHipAnalyzer


@dataclass
class CallNode:
    """Represents a node in the call graph."""
    function_name: str
    qualified_name: str
    location: Dict[str, Any]
    class_name: Optional[str] = None
    namespace: List[str] = field(default_factory=list)
    is_virtual: bool = False
    is_template: bool = False
    template_args: List[str] = field(default_factory=list)
    access_level: str = "public"
    call_type: str = "direct"  # direct, virtual, template, function_pointer
    
    # Call relationships
    callers: Set[str] = field(default_factory=set)
    callees: Set[str] = field(default_factory=set)
    
    # Analysis metadata
    call_frequency: int = 0
    recursion_depth: int = 0
    is_recursive: bool = False
    complexity_score: float = 0.0


@dataclass
class CallGraph:
    """Represents a complete call graph."""
    nodes: Dict[str, CallNode] = field(default_factory=dict)
    edges: List[Dict[str, Any]] = field(default_factory=list)
    root_functions: Set[str] = field(default_factory=set)
    virtual_call_sites: List[Dict[str, Any]] = field(default_factory=list)
    template_instantiations: List[Dict[str, Any]] = field(default_factory=list)
    
    # Statistics
    total_functions: int = 0
    total_calls: int = 0
    max_depth: int = 0
    recursive_cycles: List[List[str]] = field(default_factory=list)
    unreachable_functions: Set[str] = field(default_factory=set)


class CallGraphAnalyzer:
    """
    Analyzes C++ call graphs with support for advanced features.
    
    Handles virtual function resolution, template instantiations,
    function overloading, and inheritance-based polymorphism.
    """
    
    def __init__(self):
        """Initialize the call graph analyzer."""
        self.symbol_table: Optional[SymbolTable] = None
        self.call_graph = CallGraph()
        self.analysis_cache = {}
        self.cuda_hip_analyzer = CudaHipAnalyzer()
        
        # Analysis configuration
        self.max_depth = 50
        self.analyze_virtual_calls = True
        self.analyze_templates = True
        self.track_recursion = True
        self.analyze_gpu_kernels = True
        
        log_debug("Initialized C++ call graph analyzer with GPU support")
    
    def analyze_function_calls(self, 
                              target_function: Dict[str, Any], 
                              ast_data: Dict[str, Any], 
                              max_depth: int = None) -> Dict[str, Any]:
        """
        Analyze function calls starting from a target function.
        
        Args:
            target_function: Function to start analysis from
            ast_data: Complete AST data from parser
            max_depth: Maximum depth to analyze
            
        Returns:
            Call graph analysis results
        """
        if max_depth is not None:
            self.max_depth = max_depth
        
        self.call_graph = CallGraph()
        
        # Build internal data structures
        self._build_function_index(ast_data)
        self._build_call_relationships(ast_data)
        
        # Start analysis from target function
        root_node = self._create_call_node(target_function)
        self.call_graph.nodes[root_node.qualified_name] = root_node
        self.call_graph.root_functions.add(root_node.qualified_name)
        
        # Perform depth-first analysis
        visited = set()
        self._analyze_function_recursive(
            root_node.qualified_name, 
            ast_data, 
            visited, 
            0
        )
        
        # Post-process results
        self._detect_recursive_cycles()
        self._calculate_complexity_scores()
        self._identify_virtual_dispatch_sites()
        
        return self._format_analysis_results()
    
    def build_call_tree(self, call_graph_data: Dict[str, Any], 
                       include_external: bool = False) -> Dict[str, Any]:
        """
        Build a hierarchical call tree from call graph data.
        
        Args:
            call_graph_data: Call graph analysis results
            include_external: Whether to include external library calls
            
        Returns:
            Hierarchical call tree structure
        """
        if 'nodes' not in call_graph_data:
            return {'error': 'Invalid call graph data'}
        
        # Find root nodes (functions with no callers or explicitly marked roots)
        root_nodes = []
        for node_id, node_data in call_graph_data['nodes'].items():
            if (not node_data.get('callers') or 
                node_id in call_graph_data.get('root_functions', [])):
                root_nodes.append(node_id)
        
        if not root_nodes:
            # If no clear roots, use the first node
            root_nodes = [list(call_graph_data['nodes'].keys())[0]]
        
        # Build tree structure
        tree = {
            'root_nodes': root_nodes,
            'tree_data': {},
            'statistics': {
                'node_count': len(call_graph_data['nodes']),
                'edge_count': len(call_graph_data.get('edges', [])),
                'max_depth': call_graph_data.get('max_depth', 0),
                'recursive_calls': len(call_graph_data.get('recursive_cycles', [])),
                'virtual_calls': len(call_graph_data.get('virtual_call_sites', [])),
                'external_calls': 0
            }
        }
        
        # Build tree for each root
        for root in root_nodes:
            tree['tree_data'][root] = self._build_tree_recursive(
                root, 
                call_graph_data, 
                visited=set(), 
                depth=0,
                include_external=include_external
            )
        
        return tree
    
    def analyze_class_hierarchy(self, target_class: Dict[str, Any], 
                               ast_data: Dict[str, Any]) -> Dict[str, Any]:
        """
        Analyze class hierarchy and method call patterns.
        
        Args:
            target_class: Class to analyze
            ast_data: Complete AST data
            
        Returns:
            Class hierarchy analysis
        """
        hierarchy = {
            'class_name': target_class['name'],
            'qualified_name': target_class['qualified_name'],
            'base_classes': [],
            'derived_classes': [],
            'virtual_methods': [],
            'overridden_methods': [],
            'method_calls': [],
            'polymorphic_calls': []
        }
        
        # Build inheritance hierarchy
        hierarchy['base_classes'] = self._get_base_classes(target_class, ast_data)
        hierarchy['derived_classes'] = self._get_derived_classes(target_class, ast_data)
        
        # Analyze virtual methods
        hierarchy['virtual_methods'] = self._get_virtual_methods(target_class, ast_data)
        hierarchy['overridden_methods'] = self._get_overridden_methods(target_class, ast_data)
        
        # Analyze method calls within class
        hierarchy['method_calls'] = self._get_class_method_calls(target_class, ast_data)
        
        # Identify polymorphic call sites
        hierarchy['polymorphic_calls'] = self._identify_polymorphic_calls(target_class, ast_data)
        
        return hierarchy
    
    def analyze_gpu_call_graph(self, 
                              target_function: Dict[str, Any], 
                              ast_data: Dict[str, Any], 
                              source_code: str = None,
                              max_depth: int = None) -> Dict[str, Any]:
        """
        Analyze GPU kernel call graphs including CUDA/HIP kernels.
        
        Args:
            target_function: Function to start analysis from
            ast_data: Complete AST data from parser
            source_code: Raw source code for kernel launch analysis
            max_depth: Maximum depth to analyze
            
        Returns:
            GPU-enhanced call graph analysis results
        """
        # First do regular call graph analysis
        regular_analysis = self.analyze_function_calls(target_function, ast_data, max_depth)
        
        # Then add GPU-specific analysis
        gpu_analysis = self.cuda_hip_analyzer.analyze_gpu_code(ast_data, source_code)
        
        # Merge GPU analysis into call graph
        enhanced_analysis = regular_analysis.copy()
        enhanced_analysis['gpu_analysis'] = gpu_analysis
        
        # Add GPU-specific call graph nodes
        gpu_nodes = {}
        gpu_edges = []
        
        # Add kernel launch sites as special nodes
        for kernel_launch in gpu_analysis['kernel_launches']:
            kernel_node_id = f"kernel_launch_{kernel_launch['kernel_name']}_{kernel_launch['location'].get('line', 0)}"
            gpu_nodes[kernel_node_id] = {
                'function_name': f"<<<{kernel_launch['kernel_name']}>>>",
                'qualified_name': kernel_node_id,
                'location': kernel_launch['location'],
                'call_type': 'kernel_launch',
                'launch_style': kernel_launch['launch_style'],
                'grid_config': kernel_launch['grid_config'],
                'is_gpu_kernel': True,
                'complexity_score': self._calculate_kernel_complexity(kernel_launch)
            }
            
            # Add edge from host function to kernel
            caller_func = self._find_caller_function(kernel_launch['location'], ast_data)
            if caller_func:
                gpu_edges.append({
                    'caller': caller_func,
                    'callee': kernel_node_id,
                    'call_type': 'host_to_device',
                    'location': kernel_launch['location']
                })
        
        # Add device function calls
        for device_func in gpu_analysis['device_functions']:
            if device_func['is_kernel']:
                # Find calls within kernel
                kernel_calls = self._analyze_kernel_calls(device_func, ast_data)
                for call in kernel_calls:
                    gpu_edges.append({
                        'caller': device_func['qualified_name'],
                        'callee': call['callee'],
                        'call_type': 'device_to_device',
                        'location': call['location']
                    })
        
        # Add memory operation dependencies
        for mem_op in gpu_analysis['memory_operations']:
            mem_node_id = f"memory_op_{mem_op['function']}_{mem_op['location'].get('line', 0)}"
            gpu_nodes[mem_node_id] = {
                'function_name': mem_op['function'],
                'qualified_name': mem_node_id,
                'location': mem_op['location'],
                'call_type': 'memory_operation',
                'operation_type': mem_op['operation_type'],
                'api_type': mem_op['api_type'],
                'is_async': mem_op['is_async'],
                'complexity_score': 1.0
            }
        
        # Add synchronization points
        for sync_op in gpu_analysis['synchronization_points']:
            sync_node_id = f"sync_{sync_op['function']}_{sync_op['location'].get('line', 0)}"
            gpu_nodes[sync_node_id] = {
                'function_name': sync_op['function'],
                'qualified_name': sync_node_id,
                'location': sync_op['location'],
                'call_type': 'synchronization',
                'sync_scope': sync_op['sync_scope'],
                'complexity_score': 0.5
            }
        
        # Merge GPU nodes and edges into main analysis
        enhanced_analysis['nodes'].update(gpu_nodes)
        enhanced_analysis['edges'].extend(gpu_edges)
        
        # Update statistics
        enhanced_analysis['statistics']['gpu_kernels'] = len(gpu_analysis['kernel_launches'])
        enhanced_analysis['statistics']['device_functions'] = len(gpu_analysis['device_functions'])
        enhanced_analysis['statistics']['memory_operations'] = len(gpu_analysis['memory_operations'])
        enhanced_analysis['statistics']['synchronization_points'] = len(gpu_analysis['synchronization_points'])
        
        return enhanced_analysis
    
    def _calculate_kernel_complexity(self, kernel_launch: Dict[str, Any]) -> float:
        """Calculate complexity score for a kernel launch."""
        base_complexity = 2.0  # Base GPU kernel complexity
        
        # Add complexity based on grid configuration
        grid_config = kernel_launch.get('grid_config', {})
        
        # Try to parse grid dimensions
        grid_dim = str(grid_config.get('grid_dim', '1'))
        block_dim = str(grid_config.get('block_dim', '1'))
        
        if 'dim3' in grid_dim or ',' in grid_dim:
            base_complexity += 1.0  # 2D/3D grids are more complex
        
        if 'dim3' in block_dim or ',' in block_dim:
            base_complexity += 1.0  # 2D/3D blocks are more complex
        
        # Add complexity for shared memory usage
        shared_memory = str(grid_config.get('shared_memory', '0'))
        if shared_memory != '0':
            base_complexity += 1.5
        
        # Add complexity for stream usage
        stream = str(grid_config.get('stream', 'default'))
        if stream != 'default' and stream != '0':
            base_complexity += 0.5
        
        return base_complexity
    
    def _find_caller_function(self, location: Dict[str, Any], ast_data: Dict[str, Any]) -> Optional[str]:
        """Find the function that contains the given location."""
        if not location or 'line' not in location:
            return None
        
        target_line = location['line']
        
        # Look through all functions to find one that contains this line
        for func in ast_data.get('functions', []):
            func_location = func.get('location', {})
            if (func_location.get('line', 0) <= target_line and 
                func_location.get('end_line', target_line) >= target_line):
                return func['qualified_name']
        
        return None
    
    def _analyze_kernel_calls(self, device_func: Dict[str, Any], ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Analyze function calls within a GPU kernel."""
        kernel_calls = []
        
        # This would require more detailed analysis of the kernel function body
        # For now, return empty list as placeholder
        # In a full implementation, we would parse the kernel's AST to find device function calls
        
        return kernel_calls
    
    def _build_function_index(self, ast_data: Dict[str, Any]):
        """Build an index of all functions for quick lookup."""
        self.function_index = {}
        self.class_methods = defaultdict(list)
        self.namespace_functions = defaultdict(list)
        
        for func in ast_data.get('functions', []):
            qualified_name = func['qualified_name']
            self.function_index[qualified_name] = func
            
            # Index by class
            if func.get('class_name'):
                self.class_methods[func['class_name']].append(func)
            
            # Index by namespace
            namespace = '::'.join(func.get('namespace', []))
            self.namespace_functions[namespace].append(func)
    
    def _build_call_relationships(self, ast_data: Dict[str, Any]):
        """Build call relationships from AST data."""
        self.call_relationships = defaultdict(set)
        self.virtual_calls = []
        self.template_calls = []
        
        # Process function calls
        for call in ast_data.get('function_calls', []):
            caller = call.get('caller_function')
            callee = call.get('function_name')
            
            if caller and callee:
                self.call_relationships[caller].add(callee)
                
                if call.get('is_template_instantiation'):
                    self.template_calls.append(call)
        
        # Process method calls
        for call in ast_data.get('method_calls', []):
            caller = call.get('caller_function')
            callee = call.get('method_name')
            
            if caller and callee:
                # For method calls, we need to resolve the actual method
                resolved_method = self._resolve_method_call(call, ast_data)
                if resolved_method:
                    self.call_relationships[caller].add(resolved_method)
                    
                    # Check if this is a virtual call
                    if self._is_virtual_call(call, ast_data):
                        self.virtual_calls.append(call)
        
        # Process constructor calls
        for call in ast_data.get('constructor_calls', []):
            caller = call.get('caller_function')
            class_name = call.get('class_name')
            
            if caller and class_name:
                # Find constructor(s) for this class
                constructors = self._find_constructors(class_name, ast_data)
                for constructor in constructors:
                    self.call_relationships[caller].add(constructor['qualified_name'])
    
    def _create_call_node(self, function_data: Dict[str, Any]) -> CallNode:
        """Create a call node from function data."""
        return CallNode(
            function_name=function_data['name'],
            qualified_name=function_data['qualified_name'],
            location=function_data['location'],
            class_name=function_data.get('class_name'),
            namespace=function_data.get('namespace', []),
            is_virtual=function_data.get('is_virtual', False),
            is_template=function_data.get('is_template', False),
            access_level=function_data.get('access_level', 'public')
        )
    
    def _analyze_function_recursive(self, function_name: str, ast_data: Dict[str, Any], 
                                   visited: Set[str], depth: int):
        """Recursively analyze function calls."""
        if depth > self.max_depth or function_name in visited:
            return
        
        visited.add(function_name)
        
        # Get callees for this function
        callees = self.call_relationships.get(function_name, set())
        
        for callee in callees:
            # Create callee node if not exists
            if callee not in self.call_graph.nodes:
                callee_func = self.function_index.get(callee)
                if callee_func:
                    callee_node = self._create_call_node(callee_func)
                    self.call_graph.nodes[callee] = callee_node
            
            # Add edge
            edge = {
                'caller': function_name,
                'callee': callee,
                'call_type': self._determine_call_type(function_name, callee, ast_data),
                'location': self._get_call_location(function_name, callee, ast_data)
            }
            self.call_graph.edges.append(edge)
            
            # Update node relationships
            if function_name in self.call_graph.nodes:
                self.call_graph.nodes[function_name].callees.add(callee)
            if callee in self.call_graph.nodes:
                self.call_graph.nodes[callee].callers.add(function_name)
            
            # Recursive analysis
            self._analyze_function_recursive(callee, ast_data, visited.copy(), depth + 1)
    
    def _resolve_method_call(self, call: Dict[str, Any], ast_data: Dict[str, Any]) -> Optional[str]:
        """Resolve a method call to the actual method."""
        method_name = call.get('method_name')
        object_type = call.get('object_type', {})
        
        if not method_name:
            return None
        
        # Try to get the class type
        class_name = object_type.get('spelling', '').replace('*', '').replace('&', '').strip()
        
        if not class_name:
            return method_name
        
        # Look for method in class
        class_methods = self.class_methods.get(class_name, [])
        for method in class_methods:
            if method['name'] == method_name:
                return method['qualified_name']
        
        # If not found, return the method name as-is
        return method_name
    
    def _is_virtual_call(self, call: Dict[str, Any], ast_data: Dict[str, Any]) -> bool:
        """Check if a method call is virtual."""
        method_name = call.get('method_name')
        object_type = call.get('object_type', {})
        
        class_name = object_type.get('spelling', '').replace('*', '').replace('&', '').strip()
        
        # Find the method and check if it's virtual
        class_methods = self.class_methods.get(class_name, [])
        for method in class_methods:
            if method['name'] == method_name:
                return method.get('is_virtual', False)
        
        return False
    
    def _find_constructors(self, class_name: str, ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Find all constructors for a class."""
        constructors = []
        class_methods = self.class_methods.get(class_name, [])
        
        for method in class_methods:
            if method['name'] == class_name:  # Constructor has same name as class
                constructors.append(method)
        
        return constructors
    
    def _determine_call_type(self, caller: str, callee: str, ast_data: Dict[str, Any]) -> str:
        """Determine the type of call (direct, virtual, template, etc.)."""
        callee_func = self.function_index.get(callee)
        
        if not callee_func:
            return 'external'
        
        if callee_func.get('is_virtual'):
            return 'virtual'
        elif callee_func.get('is_template'):
            return 'template'
        else:
            return 'direct'
    
    def _get_call_location(self, caller: str, callee: str, ast_data: Dict[str, Any]) -> Dict[str, Any]:
        """Get the location where the call occurs."""
        # Look through call data to find the specific call location
        for call in ast_data.get('function_calls', []):
            if (call.get('caller_function') == caller and 
                call.get('function_name') == callee):
                return call.get('location', {})
        
        for call in ast_data.get('method_calls', []):
            resolved_method = self._resolve_method_call(call, ast_data)
            if (call.get('caller_function') == caller and 
                resolved_method == callee):
                return call.get('location', {})
        
        return {}
    
    def _detect_recursive_cycles(self):
        """Detect recursive cycles in the call graph."""
        def dfs_cycle_detection(node: str, path: List[str], visited: Set[str]):
            if node in path:
                # Found a cycle
                cycle_start = path.index(node)
                cycle = path[cycle_start:] + [node]
                self.call_graph.recursive_cycles.append(cycle)
                return
            
            if node in visited:
                return
            
            visited.add(node)
            path.append(node)
            
            # Visit callees
            node_obj = self.call_graph.nodes.get(node)
            if node_obj:
                for callee in node_obj.callees:
                    dfs_cycle_detection(callee, path.copy(), visited)
        
        visited = set()
        for node_id in self.call_graph.nodes:
            if node_id not in visited:
                dfs_cycle_detection(node_id, [], visited)
        
        # Mark recursive functions
        recursive_functions = set()
        for cycle in self.call_graph.recursive_cycles:
            recursive_functions.update(cycle)
        
        for func_name in recursive_functions:
            if func_name in self.call_graph.nodes:
                self.call_graph.nodes[func_name].is_recursive = True
    
    def _calculate_complexity_scores(self):
        """Calculate complexity scores for functions."""
        for node_id, node in self.call_graph.nodes.items():
            # Base complexity
            complexity = 1.0
            
            # Add complexity based on number of callees
            complexity += len(node.callees) * 0.5
            
            # Add complexity for virtual calls
            if node.is_virtual:
                complexity += 2.0
            
            # Add complexity for template functions
            if node.is_template:
                complexity += 1.5
            
            # Add complexity for recursive functions
            if node.is_recursive:
                complexity += 3.0
            
            node.complexity_score = complexity
    
    def _identify_virtual_dispatch_sites(self):
        """Identify virtual function dispatch sites."""
        for call in self.virtual_calls:
            dispatch_site = {
                'caller': call.get('caller_function'),
                'callee': call.get('method_name'),
                'object_type': call.get('object_type', {}),
                'location': call.get('location', {}),
                'possible_targets': self._get_virtual_targets(call)
            }
            self.call_graph.virtual_call_sites.append(dispatch_site)
    
    def _get_virtual_targets(self, call: Dict[str, Any]) -> List[str]:
        """Get possible targets for a virtual call."""
        method_name = call.get('method_name')
        object_type = call.get('object_type', {})
        
        targets = []
        
        # Get base class
        base_class = object_type.get('spelling', '').replace('*', '').replace('&', '').strip()
        
        # Find all derived classes that override this method
        # This is a simplified implementation
        for class_name, methods in self.class_methods.items():
            for method in methods:
                if (method['name'] == method_name and 
                    method.get('is_virtual') and
                    self._is_derived_from(class_name, base_class)):
                    targets.append(method['qualified_name'])
        
        return targets
    
    def _is_derived_from(self, derived_class: str, base_class: str) -> bool:
        """Check if derived_class is derived from base_class."""
        # This would need inheritance hierarchy information
        # For now, return False as a placeholder
        return False
    
    def _format_analysis_results(self) -> Dict[str, Any]:
        """Format analysis results for output."""
        # Update statistics
        self.call_graph.total_functions = len(self.call_graph.nodes)
        self.call_graph.total_calls = len(self.call_graph.edges)
        self.call_graph.max_depth = self._calculate_max_depth()
        
        # Convert nodes to dict format
        nodes_dict = {}
        for node_id, node in self.call_graph.nodes.items():
            nodes_dict[node_id] = {
                'function_name': node.function_name,
                'qualified_name': node.qualified_name,
                'location': node.location,
                'class_name': node.class_name,
                'namespace': node.namespace,
                'is_virtual': node.is_virtual,
                'is_template': node.is_template,
                'access_level': node.access_level,
                'call_type': node.call_type,
                'callers': list(node.callers),
                'callees': list(node.callees),
                'is_recursive': node.is_recursive,
                'complexity_score': node.complexity_score
            }
        
        return {
            'nodes': nodes_dict,
            'edges': self.call_graph.edges,
            'root_functions': list(self.call_graph.root_functions),
            'virtual_call_sites': self.call_graph.virtual_call_sites,
            'template_instantiations': self.call_graph.template_instantiations,
            'recursive_cycles': self.call_graph.recursive_cycles,
            'statistics': {
                'total_functions': self.call_graph.total_functions,
                'total_calls': self.call_graph.total_calls,
                'max_depth': self.call_graph.max_depth,
                'recursive_functions': len([n for n in self.call_graph.nodes.values() if n.is_recursive]),
                'virtual_functions': len([n for n in self.call_graph.nodes.values() if n.is_virtual]),
                'template_functions': len([n for n in self.call_graph.nodes.values() if n.is_template]),
                'virtual_call_sites': len(self.call_graph.virtual_call_sites)
            }
        }
    
    def _calculate_max_depth(self) -> int:
        """Calculate maximum call depth."""
        max_depth = 0
        
        def dfs_depth(node: str, current_depth: int, visited: Set[str]) -> int:
            if node in visited:
                return current_depth
            
            visited.add(node)
            
            node_obj = self.call_graph.nodes.get(node)
            if not node_obj or not node_obj.callees:
                return current_depth
            
            max_child_depth = current_depth
            for callee in node_obj.callees:
                child_depth = dfs_depth(callee, current_depth + 1, visited.copy())
                max_child_depth = max(max_child_depth, child_depth)
            
            return max_child_depth
        
        for root in self.call_graph.root_functions:
            depth = dfs_depth(root, 1, set())
            max_depth = max(max_depth, depth)
        
        return max_depth
    
    def _build_tree_recursive(self, node_id: str, call_graph_data: Dict[str, Any], 
                             visited: Set[str], depth: int, 
                             include_external: bool = False) -> Dict[str, Any]:
        """Build tree structure recursively."""
        if node_id in visited or depth > 20:  # Prevent infinite recursion
            return {
                'name': node_id,
                'type': 'recursive_reference',
                'depth': depth,
                'children': []
            }
        
        visited.add(node_id)
        
        node_data = call_graph_data['nodes'].get(node_id, {})
        
        tree_node = {
            'name': node_data.get('function_name', node_id),
            'qualified_name': node_data.get('qualified_name', node_id),
            'location': node_data.get('location', {}),
            'class_name': node_data.get('class_name'),
            'is_virtual': node_data.get('is_virtual', False),
            'is_template': node_data.get('is_template', False),
            'complexity_score': node_data.get('complexity_score', 0.0),
            'depth': depth,
            'children': []
        }
        
        # Add children
        callees = node_data.get('callees', [])
        for callee in callees:
            if callee in call_graph_data['nodes'] or include_external:
                child_tree = self._build_tree_recursive(
                    callee, call_graph_data, visited.copy(), depth + 1, include_external
                )
                tree_node['children'].append(child_tree)
        
        return tree_node
    
    def _get_base_classes(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[str]:
        """Get base classes of the target class."""
        base_classes = []
        
        # Get inheritance relations
        for relation in ast_data.get('inheritance_relations', []):
            if relation['derived_class'] == target_class['qualified_name']:
                base_classes.append(relation['base_class'])
        
        return base_classes
    
    def _get_derived_classes(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[str]:
        """Get classes derived from the target class."""
        derived_classes = []
        
        # Get inheritance relations
        for relation in ast_data.get('inheritance_relations', []):
            if relation['base_class'] == target_class['qualified_name']:
                derived_classes.append(relation['derived_class'])
        
        return derived_classes
    
    def _get_virtual_methods(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Get virtual methods of the target class."""
        virtual_methods = []
        
        class_methods = self.class_methods.get(target_class['name'], [])
        for method in class_methods:
            if method.get('is_virtual'):
                virtual_methods.append({
                    'name': method['name'],
                    'qualified_name': method['qualified_name'],
                    'is_pure_virtual': method.get('is_pure_virtual', False),
                    'is_override': method.get('is_override', False),
                    'location': method['location']
                })
        
        return virtual_methods
    
    def _get_overridden_methods(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Get methods that override base class methods."""
        overridden_methods = []
        
        class_methods = self.class_methods.get(target_class['name'], [])
        for method in class_methods:
            if method.get('is_override'):
                overridden_methods.append({
                    'name': method['name'],
                    'qualified_name': method['qualified_name'],
                    'base_method': self._find_base_method(method, target_class, ast_data),
                    'location': method['location']
                })
        
        return overridden_methods
    
    def _get_class_method_calls(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Get all method calls within the class."""
        method_calls = []
        
        class_methods = self.class_methods.get(target_class['name'], [])
        method_names = {method['name'] for method in class_methods}
        
        for call in ast_data.get('method_calls', []):
            if call.get('caller_class') == target_class['name']:
                method_calls.append({
                    'caller': call.get('caller_function'),
                    'callee': call.get('method_name'),
                    'location': call.get('location'),
                    'is_internal': call.get('method_name') in method_names
                })
        
        return method_calls
    
    def _identify_polymorphic_calls(self, target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> List[Dict[str, Any]]:
        """Identify polymorphic call sites in the class."""
        polymorphic_calls = []
        
        for call_site in self.call_graph.virtual_call_sites:
            if call_site.get('caller', '').startswith(target_class['qualified_name']):
                polymorphic_calls.append(call_site)
        
        return polymorphic_calls
    
    def _find_base_method(self, method: Dict[str, Any], target_class: Dict[str, Any], ast_data: Dict[str, Any]) -> Optional[str]:
        """Find the base class method that this method overrides."""
        # Get base classes
        base_classes = self._get_base_classes(target_class, ast_data)
        
        for base_class in base_classes:
            base_methods = self.class_methods.get(base_class, [])
            for base_method in base_methods:
                if (base_method['name'] == method['name'] and
                    base_method.get('is_virtual')):
                    return base_method['qualified_name']
        
        return None